// 解题思路：
// 到 nums[i] 可以向后最多跳 nums[i] 步，求找跳到 nums[n - 1] 位置的最小跳数
// 贪心策略：本质上就是寻找下一次起跳的最右位置
// 尽量往后跳，跳最多的距离，对应就是最少的步数
// 遍历后面的数字，跳到那个数字（j）后，往后最多能到 j + nums[j]
// 每一跳都找到最远的那个位置，直到跳到 n - 1 位置

public class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        int left = 0; int right = 0; int maxPos = 0; int step = 0;
        while(left <= right){
            if(maxPos >= n - 1){
                // 判断是否跳到最后一个位置
                return step;
            }
            for(int i = left; i <= right; i++){
                // 找这一跳最远能跳到的位置
                maxPos = Math.max(maxPos, i + nums[i]);
            }
            // 跳完加一步
            step++;
            // 更新左右区间
            left = right + 1;
            right = maxPos;
        }
        return -1;
    }
}
